package ClassLib;

import java.util.Comparator;
import java.util.PriorityQueue;

public class libof202409_binarySearch {
    //https://leetcode.cn/problems/ugly-number/description/
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        while (n % 2 == 0) n /= 2;
        while (n % 3 == 0) n /= 3;
        while (n % 5 == 0) n /= 5;
        return n == 1;
    }

    //https://leetcode.cn/problems/ugly-number-ii/
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n + 1];
        int a = 1, b = 1, c = 1;
        int p_a = 1, p_b = 1, p_c = 1;
        int p = 1;
        int cnt = n;
        while (cnt-- > 0) {
            int min_val = Math.min(p_a, Math.min(p_b, p_c));
            ugly[p++] = min_val;
            if (p_a == min_val) {
                p_a = ugly[a++] * 2;
            }
            if (p_b == min_val) {
                p_b = ugly[b++] * 3;
            }
            if (p_c == min_val) {
                p_c = ugly[c++] * 5;
            }
        }
        return ugly[n];
    }

    //https://leetcode.cn/problems/super-ugly-number/
    public int nthSuperUglyNumber(int n, int[] primes) {
        //这个元组是什么,[0]->val,[1]->index,[2]-> prime
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        long[] ugly = new long[n + 1];
        for (int prime : primes) {
            pq.offer(new long[]{1, prime, 1});
        }
        int p = 1;
        while (p <= n) {
            long[] item = pq.poll();
            long val = item[0];
            long prime = item[1];
            int idx = (int) item[2];
            if (ugly[p - 1] != val) {
                ugly[p++] = val;
            }
            pq.offer(new long[]{ugly[idx] * prime, prime, idx + 1});
        }
        return (int) ugly[n];
    }

    //https://leetcode.cn/problems/ugly-number-iii/
    public int nthUglyNumber(int n, int a, int b, int c) {

        //下面的这种方式是最容易想到的，思路还是没问题，但是要考虑其中一个prime 有1 的场景，并且他是0(n) 因此最后的用例会超时
//        if(a==1||b==1||c==1) return n;
//        int i = 1, j = 1, k = 1;
//        long res = 1;
//        int cnt = 0;
//        while (cnt < n) {
//            long p_a= (long) a * i;
//            long p_b= (long) b * j;
//            long p_k= (long) c * k;
//            long min = Math.min(p_a, Math.min(p_b, p_k));
//            if (min==p_a) {
//                i++;
//            }
//            if (min == p_b) {
//                j++;
//            }
//            if (min == p_k) {
//                k++;
//            }
//            if (res != min) {
//                res = min;
//                cnt++;
//            }
//
//        }
//        return (int) res;

      // 用二分做一下 f(sum,a,b,c) 这个函数的意思是 能被a or b or c整除的树并且在sum内有多少个，
//         int lo=1,hi=(int)2e9+1;
//      while (lo<hi){
//          int mid = lo+(hi-lo)/2;
//          int cnt=f(mid,a,b,c);
//          if(cnt>=n)
//              hi = mid;
//          else if(cnt<n)
//              lo = mid+1;
//      }
        int lo=1,hi=(int)2e9+1;
        while (lo<hi){
            int mid = lo+(hi-lo)/2;
           if(f(mid,a,b,c)>=n)
                hi = mid;
            else
                lo = mid+1;
        }
         return lo;
    }

    private long f(int sum, int a, int b, int c) {
        long a_cnt=sum/a;
        long b_cnt=sum/b;
        long c_cnt=sum/c;
        long ab_cnt=sum/(lcm(a,b));
        long ac_cnt=sum/(lcm(a,c));
        long bc_cnt=sum/(lcm(b,c));
        long abc_cnt=sum/(lcm(lcm(a,b),c));
        return  a_cnt+b_cnt+c_cnt-ab_cnt-ac_cnt-bc_cnt+abc_cnt;
    }
    private  long lcm(long a,long b){
        return  a*b/gcd(a,b);
    }
    private  long gcd(long a,long b){
        if(a<b){
            var tmp=a;
            a=b;
            b=tmp;
        }
        while (b!=0){
            var p=a%b;
            a=b;
            b=p;
        }
        return a;
    }
  //https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/
    public int takeAttendance(int[] records) {
        int lo=0,hi=records.length;
        while(lo<hi){
            int mid = lo+(hi-lo)/2;
            if(records[mid]<=mid) lo=mid+1;
            else hi=mid;
        }
        return lo;
    }
  //https://leetcode.cn/problems/first-missing-positive/
    public int firstMissingPositive(int[] nums) {
        int n=nums.length;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]<=0) nums[i]=n+1;
        }
        for (int i = 0; i < nums.length; i++) {
            int abs_ival=Math.abs(nums[i]);
            if(abs_ival<=n&& nums[abs_ival-1]>0)
                nums[abs_ival-1]=-nums[abs_ival-1];
        }
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0) return i+1;
        }
        return n+1;
    }
}
